'''
https://leetcode.cn/problems/knight-probability-in-chessboard/description/
'''
from functools import cache


class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        @cache
        def process(r, c, rest):
            if rest == 0:
                return 1
            res = 0
            for x, y in ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)):
                nr, nc = r + x, c + y
                if 0 <= nr < n and 0 <= nc < n:
                    res += process(nr, nc, rest - 1)
            return res

        return process(row, column, k) / 8 ** k

    def knightProbability2(self, n: int, k: int, row: int, column: int) -> float:
        # 第三维度依赖前面的  第一第二维度乱七八糟的依赖
        dp = [[[0] * n for _ in range(n)] for _ in range(k + 1)]
        for r in range(n):
            for c in range(n):
                dp[0][r][c] = 1
        for rest in range(1, k + 1):
            for r in range(n):
                for c in range(n):
                    res = 0
                    for x, y in ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)):
                        nr, nc = r + x, c + y
                        if 0 <= nr < n and 0 <= nc < n:
                            res += dp[rest - 1][nr][nc]
                    dp[rest][r][c] = res
        return dp[k][row][column] / 8 ** k

    # 状态压缩
    def knightProbability3(self, n: int, k: int, row: int, column: int) -> float:
        # 第三维度依赖前面的  第一第二维度乱七八糟的依赖
        A = [[1] * n for _ in range(n)]
        for rest in range(1, k + 1):
            B = [[0] * n for _ in range(n)]
            for r in range(n):
                for c in range(n):
                    res = 0
                    for x, y in ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)):
                        nr, nc = r + x, c + y
                        if 0 <= nr < n and 0 <= nc < n:
                            res += A[nr][nc]
                    B[r][c] = res
            A = B
        return A[row][column] / 8 ** k